package com.test.daily.leetcode.y2021.m11.day1129;

/**
 * @author Tom on 2021/11/29
 */
public class Code01_Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k){
        int n = arr.length;
        double left = 0.0, right = 1.0;
        while(true){
            double mid = (left + right)/2;
            int i = -1, count = 0;
            // 記錄最大的分數
            int x = 0, y = 1;
            for(int j = 1; j < n; ++j){
                while((double) arr[i+1]/arr[j] < mid){
                    ++i;
                    if(arr[i]*y > arr[j]*x){
                        x = arr[i];
                        y = arr[j];
                    }
                }
                count += i + 1;
            }
            if(count == k){
                return new int[]{x, y};
            }
            if(count < k){
                left = mid;
            }else {
                right = mid;
            }
        }
    }
}
